#include <bits/stdc++.h>
using namespace std;

/*
2829. k-avoiding 数组的最小总和
已解答
中等
相关标签
相关企业
提示
给你两个整数 n 和 k 。

对于一个由 不同 正整数组成的数组，如果其中不存在任何求和等于 k 的不同元素对，则称其为 k-avoiding 数组。

返回长度为 n 的 k-avoiding 数组的可能的最小总和。

 

示例 1：

输入：n = 5, k = 4
输出：18
解释：设若 k-avoiding 数组为 [1,2,4,5,6] ，其元素总和为 18 。
可以证明不存在总和小于 18 的 k-avoiding 数组。
示例 2：

输入：n = 2, k = 6
输出：3
解释：可以构造数组 [1,2] ，其元素总和为 3 。
可以证明不存在总和小于 3 的 k-avoiding 数组。 
 

提示：

1 <= n, k <= 50
*/

// 法一
class Solution {
	public:
	int minimumSum(int n, int k) {
		int sum  = 0;
		unordered_set<int> used;    // 用于存储已选择的元素
		for (int i = 1; n > 0; ++i) {
			int complement = k - i;
			// 当前数字和它补数都没出现过，就选择它
			if (used.find(i) == used.end() && used.find(complement) == used.end()) {
				sum += i;
				used.insert(i);
				--n;
			}
		}
		return sum;
	}
};

// 法二
// 数学优化
class Solution {
	public:
	int minimumSum(int n, int k) {
		if (n <= k / 2) {
			return arithmeticSeriesSum(1, 1, n);
		} else {
			return arithmeticSeriesSum(1, 1, k / 2) + arithmeticSeriesSum(k, 1, n - k / 2);
		}
	}

private:
	// 算数级数求和公式：S = n * (a1 + an) / 2
	int arithmeticSeriesSum(int a1, int d, int n) {
		int an = a1 + (n - 1) * d;  // 计算第n项
		return (a1 + an) * n / 2;    // 求和公式
	}
};
	
